#include "EightQueenSolver.h"
#include <QDebug>
#include <iostream>

EightQueenSolver::EightQueenSolver(int n, QMutex* mutex, QWaitCondition* wc) {
  m_n = n;
  time = 0.0f;
  resNum = 0;
  step = false;
  m_mutex = mutex;
  m_wait = wc;
  resOnly = true;

  nQueens = lastRes = nullptr;
  setN(m_n);

  m_state = FREE;
}

void EightQueenSolver::solveNQueens(int* flag, int row, int& n) {
  /***** 计算过程控制：暂停、停止 *****/
  if (isPause()) {  // 暂停
    m_wait->wait(m_mutex);
  }
  if (isStop())  // 停止
    return;

  if(!resOnly && step){ // 显示回溯过程
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
          lastRes[i][j] = nQueens[i][j];
        }
      emit oneResult();
      emit stepped();
      m_wait->wait(m_mutex);
  }

  if (row == n) {  // 得到可行解
    // 将结果保存到lastRes中，供画板读取显示
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        lastRes[i][j] = nQueens[i][j];
      }
    resNum++;
    // 向界面发送信号，更新画板
    emit oneResult();
    if (step) {
      emit stepped();
      m_wait->wait(m_mutex);
    }
    return;
  }
  /***************************/


  /***** 逐行递归 *****/
  for (int col = 0; col != n; col++) {
    // flag[col]为1表示该列可放置，0表示有冲突。斜线、反斜线同理
    if (flag[col] && flag[n + row + col] && flag[4 * n - 2 + col - row]) {
      flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 0;
      nQueens[row][col] = QUEEN;
      solveNQueens(flag, row + 1, n);
      nQueens[row][col] = NOQUEEN;
      flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 1;
    }
  }
}

void EightQueenSolver::solve() {
  m_state = RUNNING;
  if (m_mutex != nullptr)
    m_mutex->lock();
  int n = m_n;
  resNum = 0;
  mstimer.start();  // 开始记录时间

  // 创建flag数组，并开始递归
  int* flag = new int[5 * n - 2];
  for (int i = 0; i < 5 * n - 2; ++i) {
    flag[i] = 1;
  }
  solveNQueens(flag, 0, n); // 进入第一行递归

  // 收尾工作
  delete[] flag;
  time = (double)mstimer.nsecsElapsed() / (double)1000000000;

  if (isStop())
    emit stopped();
  else
    emit finish();

  if (m_mutex != nullptr)
    m_mutex->unlock();
  m_state = FREE;
  step = false;
}

bool EightQueenSolver::isValid(int row, int col, int& n) {
  // 检测列冲突
  for (int i = 0; i != row; ++i)
    if (nQueens[i][col] == QUEEN)
      return false;
  // 检测斜线冲突
  for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
    if (nQueens[i][j] == QUEEN)
      return false;
  // 检测反斜线冲突
  for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
    if (nQueens[i][j] == QUEEN)
      return false;
  return true;
}

void EightQueenSolver::setN(int n) {

  if (nQueens) {
    for (int i = 0; i < m_n; i++)
      delete[] nQueens[i];
    delete[] nQueens;
  }
  if (lastRes) {
    for (int i = 0; i < m_n; i++)
      delete[] lastRes[i];
    delete[] lastRes;
  }

  m_n = n;

  nQueens = new int*[m_n];
  for (int i = 0; i < m_n; ++i) {
    nQueens[i] = new int[m_n]();
  }
  lastRes = new int*[m_n];
  for (int i = 0; i < m_n; ++i) {
    lastRes[i] = new int[m_n]();
  }
}

void EightQueenSolver::run() {
  solve();
}

void EightQueenSolver::stopSolve() {
  m_state = STOPPED;
  step = false;
}

void EightQueenSolver::pauseSolve() {
  if (m_state == PAUSED)
    m_state = RUNNING;
  else
      m_state = PAUSED;
}

void EightQueenSolver::setResOnly(int b)
{
    if(b==Qt::Checked) resOnly=true;
    else resOnly=false;
}
